import functools
import math
from typing import List


class Solution:
    def __init__(self):
        self.nums = []
        self.size = 0
        self.gcd_lst = [[]]

    def maxScore(self, nums: List[int]) -> int:
        # 暴力解法的时间复杂度：(2n)! > 10**9
        # 状态压缩动态规划的时间复杂度：n*(2**(2n)) = 7*16384

        self.nums = nums
        self.size = len(nums)

        # 计算任意两个数的最大公因数
        self.gcd_lst = [[0] * self.size for _ in range(self.size)]
        for i in range(self.size):
            for j in range(i + 1, self.size):
                self.gcd_lst[i][j] = math.gcd(nums[i], nums[j])

        return self.dfs(1, 0)

    @functools.lru_cache(None)
    def dfs(self, now, stat):
        res = 0
        for i in range(self.size):
            if not (1 << i) & stat:  # 当前数还没有被选取的情况
                stat ^= (1 << i)
                for j in range(i + 1, self.size):
                    if not (1 << j) & stat:
                        stat ^= (1 << j)
                        res = max(res, self.dfs(now + 1, stat) + now * self.gcd_lst[i][j])
                        stat ^= (1 << j)
                stat ^= (1 << i)
        return res


if __name__ == "__main__":
    print(Solution().maxScore([1, 2]))  # 1
    print(Solution().maxScore([3, 4, 6, 8]))  # 11
    print(Solution().maxScore([1, 2, 3, 4, 5, 6]))  # 14
